package LeetCode._02_数组;

public class _1094_拼车 {
    public boolean carPooling(int[][] trips, int capacity) {
        if(trips == null || trips.length == 0 || trips[0].length == 0) return false;
        int[] diff = new int[1000];
        for (int[] trip : trips) {
            int val = trip[0];
            // 第 trip[1] 站乘客上车
            int i = trip[1];
            // 第 trip[2] 站乘客已经下车，
            // 即乘客在车上的区间是 [trip[1], trip[2] - 1]
            int j = trip[2] - 1;

            diff[i] += val;
            if(j+1< diff.length){
                diff[j+1] -= val;
            }
        }
        int[] res = new int[diff.length];
        res[0] = diff[0];
        //构造加上val后的原始数组
        for(int i=1;i<diff.length;i++){
            res[i] = res[i-1] + diff[i];
        }
        //整个行驶过程中不能有超过车容量
        for(int i=0;i<res.length;i++){
            if(res[i]>capacity) return false;
        }
        return true;
    }
}
